package puzzle.projecteuler.p100;

import java.math.BigInteger;

import puzzle.projecteuler.ContinuedFraction;
import puzzle.projecteuler.Fraction;
import puzzle.projecteuler.QuadricFraction;

public class Problem066 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		BigInteger T = BigInteger.ZERO;
		long D = -1;
		for (int d = 2; d <= 1000; d ++) {
			BigInteger t = minSolution(d);
//			System.out.println(d +"\t:\t" + t);
			if (t.compareTo(T) == 1) {
				T = t;
				D = d;
			}
		}
		System.out.println(T);
		System.out.println(D);
	}
	
	public static boolean isSquare(long n) {
		long t = (long)Math.sqrt(n);
		return n == t*t;
	}
	/**
	 * @param D
	 * @return
	 */
	public static BigInteger minSolution(int d) {
		
		if (isSquare(d)) {
			return BigInteger.ZERO;
		} else {
			QuadricFraction qf = new QuadricFraction(0,1,1,d);
			ContinuedFraction cf = qf.continuedFractionValue();
			BigInteger D = BigInteger.valueOf(d);
			int i = 1;
			while (true) {
				Fraction f = cf.fractionValue(i);
				BigInteger p = f.getNumerator();
				BigInteger q = f.getDenominator();
				if (p.multiply(p).subtract(q.multiply(q).multiply(D)).longValue() == 1) {
					return p;
				}
				i ++;
			}
		}
	}
}
